package com.test.daily.leetcode.y2022.m06.day0630.home.v02;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @author Tom on 2022/6/30
 */
public class Solution {
    public static class Edge{
        public int from;
        public int to;
        public int available;
        public Edge(int from, int to, int available){
            this.from = from;
            this.to = to;
            this.available = available;
        }
    }
    public static class Dinic{
        private int N;
        private ArrayList<ArrayList<Integer>> nexts;
        private ArrayList<Edge> edges;
        private int[] depth;
        private int[] cur;

        public Dinic(int nums){
            N  = nums + 1;
            nexts = new ArrayList<>();
            for(int i = 0; i <= N; i++){
                nexts.add(new ArrayList<>());
            }
            edges = new ArrayList<>();
            depth = new int[N];
            cur = new int[N];
        }
        public void addEdge(int u, int v, int r){
            int m = edges.size();
            edges.add(new Edge(u, v, r));
            nexts.get(u).add(m);
            edges.add(new Edge(v, u, 0));
            nexts.get(v).add(m + 1);
        }

        private boolean bfs(int s, int t){
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addFirst(s);
            boolean[] visited = new boolean[N];
            visited[s] = true;
            while(!queue.isEmpty()){
                int u = queue.pollLast();
                for (int i = 0; i < nexts.get(u).size(); i++) {
                    Edge e = edges.get(nexts.get(u).get(i));
                    int v = e.to;
                    if(!visited[v] && e.available > 0){
                        visited[v] = true;
                        depth[v] = depth[u] + 1;
                        if(v == t){
                            break;
                        }
                        queue.addFirst(v);
                    }
                }
            }
            return visited[t];
        }
        // 當前來到了s點, s可變
        //
    }
}
